#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int dx[] = {0, 1, -1, 0};
int dy[]= {1, 0, 0, -1};

bool dfs(int i, int j, int row, int col, int index, vector<vector<char> > &board, string word, vector<vector<bool> > &used)
{
    if (index == word.size()) {
        return true;
    }

   if (i < 0 || j < 0 || i >= row || j >= col || used[i][j])
       return false; 

   
    if (board[i][j] != word[index]) 
        return false;
    
    used[i][j] = true;    
    bool done = false;
    for (int k = 0; k < 4; k++) {
        if (dfs(i+dx[k], j+dy[k], row, col, index+1, board, word, used)) {
            done = true;
            break;
        }
    }
    used[i][j] = false;
    return done ? true : false;
}


class Solution {
    public:
        bool exist(vector<vector<char> > &board, string word) {
            int row = board.size();
            int col = board[0].size();
            vector<vector<bool> > used(row, vector<bool>(col, false));
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[0].size(); j++) 
                    if (dfs(i, j, row, col, 0, board, word, used))
                        return true;
            }

            return false;
        }
};

//ttest in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    vector<char> row1, row2, row3;
    row1.push_back('A');
    row1.push_back('B');
    row1.push_back('C');
    row1.push_back('E');
    row2.push_back('S');
    row2.push_back('F');
    row2.push_back('C');
    row2.push_back('S');
    row3.push_back('A');
    row3.push_back('D');
    row3.push_back('E');
    row3.push_back('E');
    vector<vector<char> > board;
    board.push_back(row1);
    board.push_back(row2);
    board.push_back(row3);


    cout << "-----------------Test 1--------------------" << endl;
    cout << "Find ABCCED" << mySolution.exist(board, "ABCCED") << endl;

    cout << "-----------------Test 2--------------------" << endl;
    cout << "Find ABCB" << mySolution.exist(board, "ABCB") << endl;


    cout << "-----------------Test 3--------------------" << endl;
    cout << "Find SEE" << mySolution.exist(board, "SEE") << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
